﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._30
{
    /*
     30. Substring with Concatenation of All Words 

         You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
         */
    public class Leetcode30
    {
        /// <summary>
        /// 刚开始一直思路在嵌套。。结果失败了。
        /// 用list又超时了。。用了键值对才对。
        /// </summary>
        /// <param name="s"></param>
        /// <param name="words"></param>
        /// <returns></returns>
        public IList<int> FindSubstring(string s, string[] words)
        {
            List<int> list = new List<int>();
            if (string.IsNullOrEmpty(s) || words.Length == 0)
                return list;
            if (s.IndexOf(words[0]) < 0)
                return list;
            Dictionary<string, int> dic = new Dictionary<string, int>();
            int tempvalue;
            foreach(string str in words)
            {
                if(dic.TryGetValue(str, out tempvalue))
                {
                    dic[str] = tempvalue + 1;
                }
                else
                {
                    dic[str] = 1;
                }
            }


            Dictionary<string, int> dicWords = new Dictionary<string, int>(dic);
            int wordLength = words[0].Length;
            string tempSubstring = "";
            int lastIndex = 0;
            int loopCount = s.Length - wordLength + 1;
            bool isRemove = false;
            for (int i = 0; i < loopCount;)
            {
                if (s.Length - i < wordLength)
                    break;
                tempSubstring = s.Substring(i, wordLength);
                if (!dicWords.TryGetValue(tempSubstring, out tempvalue))
                {
                    lastIndex++;
                    i = lastIndex;
                    if (isRemove)
                    {
                        dicWords = new Dictionary<string, int>(dic);
                    }
                    isRemove = false;
                }
                else
                {
                    isRemove = true;
                    i += wordLength;
                    if (tempvalue == 1)
                        dicWords.Remove(tempSubstring);
                    else
                        dicWords[tempSubstring] = tempvalue - 1;

                    if (dicWords.Keys.Count == 0)
                    {
                        list.Add(lastIndex);
                        lastIndex++;
                        i = lastIndex;
                        dicWords = new Dictionary<string, int>(dic);
                    }
                }
            }

            return list;

        }

        /// <summary>
        /// 做大字符串测试时要报错Output Limit Exceeded，嵌套太多
        /// </summary>
        /// <param name="s"></param>
        /// <param name="words"></param>
        /// <returns></returns>
        public IList<int> FindSubstring2(string s, string[] words)
        {
            List<int> list = new List<int>();
            if (string.IsNullOrEmpty(s) || words.Length == 0)
                return list;
            if (s.IndexOf(words[0]) < 0)
                return list;
            List<string> listWords = new List<string>(words);
            listWords.Sort();
            int iRet = -1;
            int substringLength = listWords[0].Length;
            int deleteLength = 0;
            while (s.Contains(words[0]))
            {
                List<string> leftlistWords = new List<string>(listWords);
                leftlistWords.RemoveAt(0);
                List<string> rightListWords = new List<string>(listWords);
                rightListWords.RemoveAt(0);

                List<string> leftMatch = new List<string>();
                List<string> rightMatch = new List<string>();
                int endStartIndex = s.IndexOf(listWords[0]);
                iRet = DeleteSubstring(s, leftlistWords, rightListWords, endStartIndex,
                    substringLength, true, leftMatch, rightMatch, listWords);
                if (iRet >= 0)
                {
                    list.Add(iRet + deleteLength);
                    deleteLength = iRet + listWords.Count * substringLength + deleteLength;

                    s = s.Substring(iRet + listWords.Count * substringLength);
                    continue;
                }
                else
                {
                    iRet = DeleteSubstring(s, leftlistWords, rightListWords, s.IndexOf(listWords[0]),
                        substringLength, false, leftMatch, rightMatch, listWords);
                    if (iRet >= 0)
                    {
                        list.Add(iRet + deleteLength);
                        deleteLength = iRet + listWords.Count * substringLength + deleteLength;
                        s = s.Substring(iRet + listWords.Count * substringLength);
                    }
                    else
                    {
                        deleteLength = substringLength + deleteLength;
                        s = s.Substring(endStartIndex + substringLength);
                    }
                }
            }
            return list;

        }

        private int DeleteSubstring(string s, List<string> leftlistWords, List<string> rightListWords, 
            int endStartIndex, int substringLength, bool isLeft, 
            List<string> leftMatch, List<string> rightMatch, List<string> oraginalListWords)
        {
            if (rightListWords.Count == 0)
                return endStartIndex - (oraginalListWords.Count - 1) * substringLength;
            if (leftlistWords.Count == 0)
                return endStartIndex;
            //比较的List里没有加入第一个字符串
            if (leftMatch.Count + rightMatch.Count == oraginalListWords.Count - 1)
            {

                List<string> tempList = new List<string>();
                tempList.AddRange(leftMatch);
                tempList.AddRange(rightMatch);
                tempList.Add(oraginalListWords[0]);
                tempList.Sort();
                bool isMatch = true;
                for (int i = 0; i < oraginalListWords.Count; i++)
                {
                    if (tempList[i] != oraginalListWords[i])
                    {
                        isMatch = false;
                        break;
                    }
                }

                if (isMatch)
                    return endStartIndex - (oraginalListWords.Count - 1) * substringLength;
                else
                {
                    leftlistWords.Add(leftMatch[0]);
                    leftMatch.RemoveAt(0);
                }
            }
            string strTemp = "";
            int iRet = -1;

            if (isLeft && endStartIndex >= substringLength)
            {
                //检查左边
                endStartIndex = endStartIndex - substringLength;
                strTemp = s.Substring(endStartIndex, substringLength);
                if (leftlistWords.Remove(strTemp))
                {
                    leftMatch.Add(strTemp);
                    iRet = DeleteSubstring(s, leftlistWords, rightListWords, endStartIndex, substringLength, true, leftMatch, rightMatch, oraginalListWords);
                    if (iRet >= 0)
                        return iRet;
                }
            }
            else
            {
                //检查右边
                endStartIndex = endStartIndex + substringLength;
                if (s.Substring(endStartIndex).Length < substringLength)
                    return -1;
                strTemp = s.Substring(endStartIndex, substringLength);
                if (rightListWords.Remove(strTemp))
                {
                    rightMatch.Add(strTemp);
                    iRet = DeleteSubstring(s, leftlistWords, rightListWords, endStartIndex, substringLength, false, leftMatch, rightMatch, oraginalListWords);
                    if (iRet >= 0)
                        return iRet;
                }
            }
            return -1;
        }

    }
}
